#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> Input;
        int i = 0;
        while (i < tokens.size())
        {
            string token = tokens[i];
            int num;
            if (isdigit(token[0]) || ((token.size() != 1) && (token[0] == '-')))
            {
                num = stoi(token);
                //Input.push(stoi(token));
                Input.push(num);
            }
            else
            {
                auto x = Input.top();
                Input.pop();
                auto y = Input.top();
                Input.pop();
                switch (token[0]) {
                case '+':
                    Input.push(y + x);
                    break;
                case '-':
                    Input.push(y - x);
                    break;
                case '*':
                    Input.push(y * x);
                    break;
                case '/':
                    Input.push(y / x);
                    break;
                default:
                    break;
                }
            }
            i++;
        }
        return Input.top();
    }
};

void test1()
{
    stack<char> S;
    char x, y;
    x = 'n'; y = 'g';
    S.push(x); S.push('i'); S.push(y);
    S.pop(); S.push('r'); S.push('t'); S.push(x);
    S.pop(); S.push('s');
    while (!S.empty())
    {
        x = S.top();
        S.pop();
        cout << x;
    };
    cout << y;

}

void test2()
{
    queue<char> Q;
    char x, y;
    x = 'n'; y = 'g';
    Q.push(x); Q.push('i'); Q.push(y);
    Q.pop(); Q.push('r'); Q.push('t'); Q.push(x);
    Q.pop(); Q.push('s');
    while (!Q.empty())
    {
        x = Q.front();
        Q.pop();
        cout << x;
    };
    cout << y;
}


int main()
{
    //string s = "13";

    //cout << stoi(s) << endl;
    //for (auto e : s)
    //{
    //    cout << e << " ";
    //}
    //cout << endl;

    //"10","6","9","3","+","-11","*","/","*","17","+","5","+"

    Solution s;
    vector<string> vs;
    vs.push_back("10");
    vs.push_back("6");
    vs.push_back("9");
    vs.push_back("3");
    vs.push_back("+");
    vs.push_back("-11");
    vs.push_back("*");
    vs.push_back("/");
    vs.push_back("*");
    vs.push_back("17");
    vs.push_back("+");
    vs.push_back("5");
    vs.push_back("+");

    int ret = s.evalRPN(vs);
    cout << ret << endl;

    test2();
}




